package com.lrs.java.dataStructure.array;

public class OrderedArray {

	private long[] arr;
	private int nElems = 0;
	
	public OrderedArray(int capacity) {
		arr = new long[capacity];
	}

	public int size() {
		return nElems;
	}
	
	public void insert(long value) {
		int i;
		//order by asc
		for(i=0; i<nElems; i++) {
			if(value < arr[i]) {
				break;
			}
		}
		if(i==nElems) {
			arr[nElems++] = value;
		} else {
			for(int k=nElems; k>i; k--) {	//linear insert
				arr[k] = arr[k-1];
			}
			arr[i] = value;
			nElems++;
		}
	}
	
	public boolean delete(long value) {
		int i=0;
		for(;i<nElems;i++) {
			if(arr[i] == value) {
				break;
			} else if(arr[i] > value) {
				return false;
			}
		}
		for(int k=i; k<nElems-1; k++) {
			arr[k] = arr[k+1];
		}
		nElems--;
		return true;
	}
	
	public int binarySearch(long value) {
		int lowerBound = 0;
		int upperBound = nElems - 1;
	
		while(true) {
			int middle = (lowerBound + upperBound)/2;
			
			if(arr[middle] == value) {
				return middle;
			} else if(lowerBound > upperBound){
				return nElems;
			} else {
				if(arr[middle] < value) {
					lowerBound = middle + 1;
				} else {
					upperBound = middle - 1;
				}
			}
		}
		
	}
	
	public void display() {
		for (int i = 0; i < nElems; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
}

class OrderedArrayApp {

	public static void main(String[] args) {
		
		OrderedArray arr = new OrderedArray(10);
		
		arr.insert(3);
		arr.insert(23);
		arr.insert(26);
		arr.insert(16);
		arr.insert(7);
		arr.insert(12);
		
		System.out.println("arr's size: " + arr.size());
		arr.display();
		
		arr.delete(16);
		System.out.println("arr's size: " + arr.size());
		arr.display();
		
	}
}

